/**
 *  @file FindCommonNode.c
 *  @desc 查找两个递增有序双向链表的公共元素，并构建一个新链表保存公共结点
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-22 16:18
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个节点
    struct node *pre;       ///< 指向上一个节点
} node, *link;

// ------------------------- 基础操作 -------------------------

/**
 * @brief 创建一个带数据的新节点
 * @param value 节点的数据
 * @return 创建成功返回新节点指针，否则返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;

    return newNode;
}

/**
 * @brief 初始化一个空链表（仅创建头结点）
 * @param head 指向链表头指针的指针
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0; // 头结点的数据不参与存储

    *head = newNode;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法插入结点（新结点插入到第一个有效结点之前）
 * @param head 链表头指针
 * @param value 要插入的数据值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre  = head;

    if (head->next != NULL) {
        head->next->pre = newNode;
    }

    head->next = newNode;
}

/**
 * @brief 尾插法插入结点（新结点插入到链表末尾）
 * @param head 链表头指针
 * @param value 要插入的数据值
 */
void istTail(link head, int value) {
    link cur = head;

    // 移动到尾部
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 正向打印链表数据（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 删除操作 -------------------------

/**
 * @brief 删除指定位置的结点（位置从 1 开始）
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;

    int idx = 1;
    link cur = head->next;

    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    if (cur->pre != NULL) {
        cur->pre->next = cur->next;
    }
    if (cur->next != NULL) {
        cur->next->pre = cur->pre;
    }

    free(cur);
}

/**
 * @brief 在链表第 pos 个位置插入值（等价于在第 pos 个结点前插入）
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入位置（从 1 开始）
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;

    link cur = head;
    int idx = 0;

    // 找到插入位置前一个结点
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre  = cur;

    if (cur->next != NULL) {
        cur->next->pre = newNode;
    }
    cur->next = newNode;
}

// ------------------------- 长度计算 -------------------------

/**
 * @brief 获取链表长度（不含头结点）
 * @param head 链表头指针
 * @return 返回链表有效结点个数
 */
int getLength(link head) {
    int length = 0;
    if (head == NULL || head->next == NULL) return length;

    link cur = head->next;
    while (cur != NULL) {
        length++;
        cur = cur->next;
    }

    return length;
}

// ------------------------- 查找公共结点 -------------------------

/**
 * @brief 查找两个链表的第一个公共结点（指针相同）
 * @param la 第一个链表头指针
 * @param lb 第二个链表头指针
 * @return 如果存在公共结点，返回该结点指针；否则返回 NULL
 */
link findFirstCommonNode(link la, link lb) {
    if (la == NULL || la->next == NULL) return NULL;
    if (lb == NULL || lb->next == NULL) return NULL;

    int lengA = getLength(la);
    int lengB = getLength(lb);

    link pa = la->next;
    link pb = lb->next;

    int dif = lengA - lengB;

    // 先对齐两个链表的长度
    if (dif > 0) {
        while (dif-- > 0) {
            pa = pa->next;
        }
    } else {
        while (dif++ < 0) {
            pb = pb->next;
        }
    }

    // 同步遍历查找第一个相同地址的结点
    while (pa && pb) {
        if (pa == pb) {
            return pa;
        }
        pa = pa->next;
        pb = pb->next;
    }

    return NULL;
}

// ------------------------- 主函数测试 -------------------------

/**
 * @brief 主函数，测试两个链表的公共结点查找
 */
int main() {
    // 初始化两个链表（带头结点）
    link head1 = NULL, head2 = NULL;
    initNode(&head1);
    initNode(&head2);

    // 创建公共部分链表：6 → 7
    link common = createNode(6);
    common->next = createNode(7);

    // 构造链表1：1 → 2 → 3 → 6 → 7
    istHead(head1, 3);
    istHead(head1, 2);
    istHead(head1, 1);

    // 移动到链表1末尾并接入公共部分
    link p = head1;
    while (p->next != NULL) p = p->next;
    p->next = common;

    // 构造链表2：4 → 5 → 6 → 7
    link node5 = createNode(5);
    node5->next = common;

    link node4 = createNode(4);
    node4->next = node5;

    head2->next = node4;

    // 打印链表1和链表2
    printf("List 1:\n");
    printList(head1);

    printf("List 2:\n");
    printList(head2);

    // 查找并打印第一个公共结点
    link result = findFirstCommonNode(head1, head2);
    if (result) {
        printf("first common node value is %d\n", result->data);
    } else {
        printf("no common node found.\n");
    }

    return 0;
}
